package com.jzoffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/*
* 请实现一个函数按照之字形打印二叉树，
* 即第一行按照从左到右的顺序打印，
* 第二层按照从右至左的顺序打印，
* 第三行按照从左到右的顺序打印，
* 其他行以此类推。
*
* */
public class PrintBinaryTreeByZhiCharacter {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(6);
        TreeNode t4 = new TreeNode(8);
        TreeNode t5 = new TreeNode(4);
        t1.left = t2;
        t2.right = t3;
        t1.right = t4;
        t4.left = t5;
        ArrayList<ArrayList<Integer>> print = print(t1);
        System.out.println(Arrays.toString(print.toArray()));

    }

    public static ArrayList<ArrayList<Integer>> print(TreeNode pRoot){
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        int floor = 1;

        while (!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0;i < size;i++){
                TreeNode treeNode = queue.poll();
                if((floor & 1 )== 0){
                    list.add(0,treeNode.val);
                }else{
                    list.add(treeNode.val);
                }
                if(treeNode.left != null){
                    queue.offer(treeNode.left);
                }
                if(treeNode.right != null){
                    queue.offer(treeNode.right);
                }
            }
            res.add(list);
            floor++;
        }
        return res;
    }
}
